This invention relates to methods for distributing traffic among routes in packetized communication networks.
Communication networks transport information between terminal communication devices such as computer terminals, telephones, facsimile machines, and computer file servers. A typical network includes switching nodes such as nodes 10.1-10.8 of FIG. 1, interconnected by links, such as links 15.1-15.10 of the figure. Generally, each terminal device (not shown) is associated with one of the nodes.
In many modern networks, the information to be transported from a source node to a destination node is divided into packets or cells. In accordance, for example, with Asynchronous Transfer Mode protocols (ATM) or Internet Protocol (IP), these, e.g., packets stream independently through the network from the source node to the destination node. At each node encountered along the way, a packet is directed into one link or another according to header information borne by that packet. We will refer to any such network as a xe2x80x9cpacketizedxe2x80x9d network.
Some communicative transactions, such as telephone calls, are highly sensitive to the timing of the packet arrivals at the destination. If there are significant absolute or relative delays, or if the packets arrive out of order, the quality of the call may be deemed unacceptable. To preserve the quality of transactions of this kind, it is desirable to maintain a complete route from the source to the destination for the entire duration of the transaction. (We will refer to communicative transactions, generally, as xe2x80x9ccalls,xe2x80x9d even if they involve the transmission of fax images, data, etc.)
In all but the simplest networks, more than one route will generally be available from a given source to a given destination. For example, it will be apparent from FIG. 1 that there are five potential routes from node 10.3 to node 10.4. However, it is not always desirable to make available every potential route for a given source-destination pair. For example, some routes may pass through an excessive number of links (i.e., they have many xe2x80x9chopsxe2x80x9d), which add an unacceptable cumulative delay. The problem is compounded by the fact that each link has a limited amount of bandwidth. Therefore, routing a call between nearby nodes through a far distant link may exclude some traffic between nodes that are situated close to that link. The result may be to force some of that traffic onto undesirably long routes as well.
The discipline referred to as xe2x80x9ctraffic engineeringxe2x80x9d deals, inter alia, with the problem of how to distribute traffic among permissible routes. This distribution is desirably made in a manner directed toward a desired level of network performance. Traffic engineering problems are further complicated when the network is required to carry more than one class of service. For example, the same network may be required to carry voice, video, fax, and e-mail transmissions. Each of these services has its own bandwidth requirements, and each has its own requirements as to how much delay can be tolerated. Each may also have its own requirements as to how much call blocking can be tolerated. A network that carries more than one class of service is here referred to as a xe2x80x9cmultiservice network.xe2x80x9d
Network traffic can be broadly divided into two categories: Quality-of-Service (QoS) traffic, and Best-Effort (BE) traffic.
QoS traffic is traffic which must satisfy critical requirements in order to be acceptable to customers. Such requirements typically relate to the maximum acceptable delay. However, they may involve other performance parameters. For example, parameters related to blocking could be important. Parameters of that type include the call-loss ratio and the packet-loss ratio. It often happens that in order to satisfy QoS requirements, the pertinent traffic must be limited to certain sets of admissible routes. This notion of admissible route sets makes it convenient, within QoS methodologies, to define admissible route sets that are limited so as to comply with policy constraints of various kinds.
QoS traffic can be further subdivided into real-time traffic, and non-real-time traffic. Real-time traffic, which includes, e.g., voice and video traffic, is meant to be utilized by the customer as it arrives. Any delays which the customer perceives as disrupting the smooth flow of received data will generally be unacceptable. Non-real-time traffic, which includes, e.g., traffic to and from facsimile machines, is more tolerant of delay, but it still must meet customer expectations of prompt and relatively smooth delivery. In particular, premium data traffic might have critical limitations on the call-loss ratio and packet-loss ratio.
BE traffic, which includes, e.g., World Wide Web traffic, e-mail, and FTP, is still more tolerant of delay as well as call blocking. The user is generally satisfied to wait minutes, or in some cases, even hours, to receive a complete message. Therefore, the network service provider is not expected to guarantee any particular limits on the maximum delay. Instead, it is generally sufficient for the network to use bandwidth, as it becomes available, that can be spared without blocking more lucrative QoS traffic.
In order for network service providers to most fully exploit their multiservice networks, it is desirable for them to offer guarantees to their customers that limits on, e.g., the amount of delay, specified variously for different service classes, will be met. However, it is difficult to design a network that will honor such guarantees without blocking an undue amount of traffic. For example, if voice traffic is concentrated on certain links because they are essential for the shortest routing of voice calls, facsimile transmissions may be excluded from these links. If these links are necessary for the routing of facsimile transmissions, the result will be a busy signal whenever an attempt is made to send a facsimile.
One approach to traffic engineering in multiservice networks is described in D. Mitra, et al., xe2x80x9cATM Network Design and Optimization: A Multirate Loss Network Framework,xe2x80x9d IEEE/ACM Transactions on Networking 4 (August 1996) 531-543. This paper describes a software package referred to as TALISMAN. Among other things, TALISMAN solves a joint routing problem in multiservice ATM networks so as to maximize a performance measure that may be characterized as the long-run average revenue for the network. (A joint routing problem is one that jointly treats all pertinent source-destination pairs.) In the TALISMAN model, a revenue figure is obtained for each service route (i.e., a route in association with a given service class) as the product of a service-route revenue parameter, times the intensity of accepted traffic on that service route. Traffic intensity is defined as the arrival rate of calls, times the mean holding time per call. These revenue figures are summed over all streams and, for each stream, over all service routes, to obtain the total network revenue. A stream is defined as a source-destination pair in association with a given service class.
There is a growing demand for multiservice networks in which the route sets available to different service classes must satisfy distinct policy requirements. In addition to traditional requirements related, e.g., to bandwidth and delay, there are further requirements related to virtual private network services, which are also in growing demand.
Generally, as the size and complexity of networks increases, the time required to solve traffic engineering problems also increases. In order to make the most efficient use of a network in the face of changing traffic patterns, it is desirable to carry out on-line solutions of traffic engineering problems; that is, solutions that are responsive to actual conditions as they occur. Even with the help of tools such as TALISMAN, this is not always feasible for networks that are large or complex.
We have invented a method for solving traffic engineering problems in a network having at least one QoS service class and at least one class of service that is not a QoS class. The computational complexity of our method is polynomial, so that there are feasible solutions even for networks having hundreds of nodes and many service classes. When applied to networks of typical size, our method will be fast enough, in many cases, to perform on-line.
In accordance with our method, bandwidth is allocated to respective service routes in at least one QoS service class. We are using the term xe2x80x9cQoSxe2x80x9d in a broad sense, to include any class of service receiving priority treatment. Both delay-sensitive and delay-insensitive traffic may be QoS traffic, in this sense. The bandwidth allocation is made in response to a given set of demands for bandwidth, in the QoS class, between each source-destination pair. Linear programming methods, such as Multicommodity Flow (MCF) techniques, are used to make this allocation in such a way as to optimize a suitable figure of merit, such as network revenue.
Then, linear programming methods are again used to make a new allocation, which minimizes network usage without departing from the optimal value of the figure of merit. Then, a residual network is identified. The residual network consists of that bandwidth that remains unallocated, on each link of the network.
A routing problem is then solved for at least one non-QoS service class. Without limitation, all such service classes are here referred to as BE classes. The routing problem is solved to find route sets for all flows in the BE service class, and to allocate bandwidth to the respective service routes in each of these route sets. This problem is solved using linear programming techniques in such a way as to optimize a suitable figure of merit, such as network revenue from best-effort traffic.
The priority of the QoS classes is enforced by routing QoS demands before, and without regard to, the BE demands. Typically, the effective bandwidths associated with the QoS services are larger than those of the BE classes. Both of these factors will generally lead to lower delay, and to lower rates of call blocking and packet loss, in the QoS traffic relative to the BE traffic.
In preferred embodiments of the invention, the routing problem for the QoS classes is solved using a route-based formulation so that specifications of limited, admissible route sets are readily accommodated. By contrast, the routing problem for the BE classes is preferably solved using a link-based formulation. (Such a formulation is sometimes referred to as xe2x80x9cedge-based.xe2x80x9d) A link-based formulation provides improved speed when problems are solved on highly connected networks. However, the link-based formulation alone does not lead to a complete solution. In a given service class, it leads to a link-by-link allocation of bandwidth associated with respective source-destination pairs, but it does not provide an allocation by service route. A further procedure, referred to as route decomposition, is used to construct, from the link-based solution, an allocation of bandwidth by service route.
In another aspect, the invention involves the use of linear programming techniques, as described above, to allocate bandwidth among service routes in response to a set of demands in each pertinent service class. Significantly, the demands are calculated so as to take into account an effective bandwidth associated with the pertinent service class, and so as to make allowance for the stochastic behavior of the traffic demands that occur in practice.
It should be noted that the traffic engineering problem that is solved by the invention in either aspect is a combined problem of routing and admission control. The routing aspect takes place explicitly as demand between a given source-destination pair in a given service class is allocated among its admissible routes. The admission-control aspect takes place implicitly when the optimum such allocation is an allocation of less than all the demand. Simply stated, admission control operates when traffic is dropped in order, e.g., to maximize revenue.